package leetcod_300;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * <p>
 * solution 1
 * ByViolated
 * 排列组合 所有可能 判断是否符合
 * 无效的情况 左括号 和 右括号数量不对等
 */
public class leetCode_22_GenerateParentheses {
    /**
     * 时间复杂度(2的2n次方 * n)
     * 空间复杂度( O（n） )
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        ArrayList<String> combinations = new ArrayList();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    /**
     * @param current 当前字符串长
     * @param pos     当前长度
     * @param result  结果列表
     */
    public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (isValid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }

    }

    //验证是否符合
    public boolean isValid(char[] current) {
        int balance = 0;
        for (char c : current) {
            if (c == '(') balance++;
            else balance--;
            //右括号不能在左括号左边
            if (balance < 0) return false;
        }
        return (balance == 0);
    }

    /**
     * @param n
     * @return
     */
    public List<String> generateParenthesisByBackTracking(int n) {
        List<String> ans = new ArrayList();
        bastrack(ans, "", 0, 0, n);
        return ans;
    }

    /**
     * @param ans
     * @param cur   当前字符串
     * @param left  左括号数量
     * @param right 右括号数量
     * @param n     最大量n
     */
    private void bastrack(List<String> ans, String cur, int left, int right, int n) {
        if (cur.length() == n * 2) {
            ans.add(cur);
            return;
        }
        if (left < n) {
            bastrack(ans, cur + "(", left + 1, right, n);
        }
        if (right < left) {
            bastrack(ans, cur + ")", left, right + 1, n);
        }
    }

    /**
     * @param n
     * @return
     */
    public List<String> generateParenthesisByEnumeration(int n) {
        List<String> ans = new ArrayList<>();
        if (n == 0) {
            ans.add("");
        } else {
            for (int a = 0; a < n; a++) {
                for (String left : generateParenthesisByEnumeration(a))
                    for (String right : generateParenthesisByEnumeration(n - 1 - a)) {
                        ans.add("(" + left + ")" + right);
                    }
            }
        }
        return ans;
    }

}
